/*
 * Copyright (c) 2009, Andrey Shvetsov
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 */

/*
 * This is version of xintlib without recursive templates.
 * To use this version fix content of 'xintlib.h'
 */

#ifndef _XINTLIB2_H
#define	_XINTLIB2_H


namespace xintlib {

    template <class UNIT, int N>
    struct base_algo
    {
        template <class T>
        static T &for_each(UNIT *p, T &t) {
            for( int i = 0; i < N; i++ )
                t( *--p );
            return t;
        }

        template <class T>
        static T &for_each_r(UNIT *p, T &t) {
            for( int i = 0; i < N; i++ )
                t( *p++ );
            return t;
        }
    };

} // namespace xintlib


namespace xintlib {

    template<int MIN_NBITS, class UNIT = unsigned, int BITS_PRO_CHAR = 8>
    struct xint
    {
    private:
        typedef unsigned long long BIGGER_TYPE;

        // mission impossible if check below fails
        enum { _compiletime_check = 1/int( sizeof(BIGGER_TYPE)>sizeof(UNIT) ) };

    public:
        enum {
            BITS_PRO_UINT = sizeof(UNIT) * BITS_PRO_CHAR,
            N = (MIN_NBITS+BITS_PRO_UINT-1)/BITS_PRO_UINT
        };

        typedef UNIT unit_type;
        typedef const UNIT const_unit_type;
        typedef base_algo<UNIT,N> algo;
        typedef base_algo<const UNIT,N> const_algo;

        xint(UNIT u = 0) {
            UNIT *p = raw_array;
            *p++ = u;
            for( int i = 1; i < N; i++ )
                *p++ = 0;
        }

        xint(const xint &x) {
            UNIT *pl = raw_array;
            const UNIT *pr = x.raw_array;
            for( int i = 0; i < N; i++ )
                *pl++ = *pr++;
        }

        xint &operator+=(const xint &x) {
            UNIT carry = 0;
            for( int i = 0; i < N; i++ )
            {
                BIGGER_TYPE const hack = BIGGER_TYPE( raw_array[i] ) + x.raw_array[i] + carry;
                raw_array[i] = hack;
                carry = hack >> BITS_PRO_UINT;
            }

            return *this;
        }

        xint &operator-=(const xint &x) {
            UNIT carry = 1;
            for( int i = 0; i < N; i++ )
            {
                BIGGER_TYPE const hack = BIGGER_TYPE( raw_array[i] ) + UNIT( ~x.raw_array[i] ) + carry;
                raw_array[i] = hack;
                carry = hack >> BITS_PRO_UINT;
            }

            return *this;
        }

        bool operator<(const xint &x) const {
            UNIT const mask = UNIT(1) << ( BITS_PRO_UINT - 1 );
            const UNIT *pl = raw_array + N;
            const UNIT *pr = x.raw_array + N;
            if( *--pl != *--pr )
                return (mask ^ *pl) < (mask ^ *pr);

            for( int i = 1; i < N; i++ )
                if( *--pl != *--pr )
                    return *pl < *pr;

            return false;
        }

        bool operator<=(const xint &x) const {
            UNIT const mask = UNIT(1) << ( BITS_PRO_UINT - 1 );
            const UNIT *pl = raw_array + N;
            const UNIT *pr = x.raw_array + N;
            if( *--pl != *--pr )
                return (mask ^ *pl) < (mask ^ *pr);

            for( int i = 1; i < N; i++ )
                if( *--pl != *--pr )
                    return *pl < *pr;

            return true;
        }

        bool operator==(const xint &x) const {
            const UNIT *pl = raw_array + N;
            const UNIT *pr = x.raw_array + N;
            for( int i = 0; i < N; i++ )
                if( *--pl != *--pr )
                    return false;

            return true;
        }

        UNIT raw_array[N];
    };

} // namespace xintlib


namespace xintlib {

    template<class XINT>
    inline bool operator>(const XINT &a, const XINT &b) {
        return !( a <= b );
    }

    template<class XINT>
    inline bool operator>=(const XINT &a, const XINT &b) {
        return !( a < b );
    }

    template<class XINT>
    inline bool operator!=(const XINT &a, const XINT &b) {
        return !( a == b );
    }

    template<class XINT>
    inline XINT operator+(const XINT &a, const XINT &b) {
        return XINT( a ) += b;
    }

    template<class XINT>
    inline XINT operator-(const XINT &a, const XINT &b) {
        return XINT( a ) -= b;
    }

    template<class XINT>
    inline XINT operator-(const XINT &x) {
        return XINT() -= x;
    }

    template<class XINT>
    inline XINT operator+(const XINT &x) {
        return XINT( x );
    }

} // namespace xintlib


namespace xintlib {

    template <class XINT, class T>
    inline T &for_each_unit(XINT &x, T &t) {
        return XINT::algo::for_each( x.raw_array + XINT::N, t );
    }

    template <class XINT, class T>
    inline const T &for_each_unit(XINT &x, const T &t) {
        return XINT::algo::for_each( x.raw_array + XINT::N, t );
    }

    template <class XINT, class T>
    inline T &for_each_unit(const XINT &x, T &t) {
        return XINT::const_algo::for_each( x.raw_array + XINT::N, t );
    }

    template <class XINT, class T>
    inline const T &for_each_unit(const XINT &x, const T &t) {
        return XINT::const_algo::for_each( x.raw_array + XINT::N, t );
    }

    template <class XINT, class T>
    inline T &for_each_unit_r(XINT &x, T &t) {
        return XINT::algo::for_each_r( x.raw_array, t );
    }

    template <class XINT, class T>
    inline const T &for_each_unit_r(XINT &x, const T &t) {
        return XINT::algo::for_each_r( x.raw_array, t );
    }

    template <class XINT, class T>
    inline T &for_each_unit_r(const XINT &x, T &t) {
        return XINT::const_algo::for_each_r( x.raw_array, t );
    }

    template <class XINT, class T>
    inline const T &for_each_unit_r(const XINT &x, const T &t) {
        return XINT::const_algo::for_each_r( x.raw_array, t );
    }

} // namespace xintlib


#endif	/* _XINTLIB2_H */
